package com.chj.jz.dp.class05;

// https://www.jiuzhang.com/problem/longest-palindromic-subsequence/#tag-lang-java
public class Code14_LongestPalindromicSubsequence {
	public static int longestPalindromeSubseq(String s) {
        char[] ss = s.toCharArray();
        int n = ss.length;
        if (n == 0) {
            return 0;
        }
        
        if (n == 1) {
            return 1;
        }
        
        int[][] f = new int[n][n];
        int[][] pi = new int[n][n];
        int i, j, len;
        
        for (i = 0; i < n; ++i) {
            f[i][i] = 1;
        }
        
        for (i = 0; i < n - 1; ++i) {
            if (ss[i] == ss[i + 1]) {
                f[i][i + 1] = 2;
            }
            else {
                f[i][i + 1] = 1;
            }
        }
        
        for (len = 3; len <= n; len++) {
            for (i = 0; i <= n - len; i++) {
                j = i + len - 1;
                f[i][j] = Math.max(f[i][j - 1], f[i + 1][j]);
                if(f[i][j] == f[i + 1][j]) {
                	pi[i][j] = 0;
                }else {
                	pi[i][j] = 1;
                }
                
                if (ss[i] == ss[j]) {
                    f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
                    if(f[i][j] == f[i + 1][j - 1] + 2) {
                    	pi[i][j] = 2;
                    }
                }
            }
        }
       
        char[] res = new char[f[0][n - 1]];
        int p = 0, q = f[0][n - 1] - 1;
        i = 0;
        j = n - 1; 
        while(i <= j){
        	if(i == j) {
        		res[p] = ss[i];
        		break;
        	}
        	
        	if(i + 1 == j) {
        		res[p] = ss[i];
        		res[q] = ss[j];
        		break;
        	}
        	
        	if(pi[i][j] == 0) {
        		i++;
        		
        	}else {
        		if(pi[i][j] == 1) {
        			j--;
        			
        		}else {
        			res[p++] = ss[i];
        			res[q--] = ss[j];
        			i++;
        			j--;
        		}
        	}
        }
        
        for(i = 0; i < f[0][n - 1]; i++) {
        	System.out.print(res[i]);
        }
        System.out.println();
        
        return f[0][n - 1];
    }
	
	static int[][] f = null;
    static char[] s = null;
    static int n = 0;

    private static void Compute(int i, int j) {
        if (f[i][j] != -1) {
            return;
        }

        if (i == j) {
            f[i][j] = 1;
            return;
        }

        if (i + 1 == j) {
            f[i][j] = (s[i] == s[j]) ? 2 : 1;
            return;
        }

        Compute(i + 1, j);
        Compute(i, j - 1);
        Compute(i + 1, j - 1);
        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
        if (s[i] == s[j]) {
            f[i][j] = Math.max(f[i][j], f[i + 1][j - 1] + 2);
        }
    }

    public static int longestPalindromeSubseqCache(String ss) {
        s = ss.toCharArray();
        n = s.length;
        if (n == 0) {
            return 0;
        }
        
        if (n == 1) {
            return 1;
        }
        
        int i, j;
        f = new int[n][n];    
        for (i = 0; i < n; ++i) {
            for (j = i; j < n; ++j) {
                f[i][j] = -1;
            }
        }
        
        Compute(0, n - 1);       
        
        return f[0][n - 1];
    }

	
	 public static void main(String[] args) {
			{
				String str = "bbbab";
				System.out.println(longestPalindromeSubseqCache(str));
			}
			{
				String str = "bbbbb";
				System.out.println(longestPalindromeSubseqCache(str));
			}
	    }
}
